#pragma once
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
//////////////////////////////////////////////////////////////
template <class T>
class Comp
{
public:
    bool operator()(const T& val1, const T& val2)
    {
        return val1 == val2;
    }
};

template<>
class Comp<string>
{
public:
    bool operator()(const string& s1, const string& s2)
    {
        return strcmp(s1.c_str(), s2.c_str()) == 0;
    }
};
////////////////////////////////////////////////////////////
template<class T>
class GetInt
{
public:
    size_t operator()(const T& val)
    {
        return (size_t)val;
    }
};

template<>
class GetInt<string>
{
public:
    size_t operator()(const string& s)
    {
        size_t ret = 0;
        for(auto& e : s)
        {
            ret += e;
            ret *= 131;
        }
        return ret;
    }
};
////////////////////////////////////////////////////////////
template <class T>
struct HashListNode
{
    explicit HashListNode(const T& val)
            : _val(val)
            , _next(nullptr)
    {}

    T _val;
    HashListNode<T>* _next;
};
////////////////////////////////////////////////////////////

template <class K, class T, class TOfK, class GetInt>
struct Hash_Iterator
{
    typedef HashListNode<T> Node;
    typedef Hash_Iterator<K, T, TOfK, GetInt> Self;

    Hash_Iterator(Node* node, vector<Node*>* v)
            : _hash_node(node)
            , _v(v)
    {}

    T& operator*()
    {
        return _hash_node->_val;
    }


    T* operator->()
    {
        return &_hash_node->_val;
    }

    Self& operator++()
    {
        if(_hash_node->_next)
        {
            _hash_node = _hash_node->_next;
        }
        else
        {
            TOfK t_of_k;
            GetInt get_int;
            int hash_pos = get_int(t_of_k(_hash_node->_val)) % _v->size();
            ++hash_pos;

            while(hash_pos < _v->size())
            {
                if((*_v)[hash_pos] != nullptr)
                {
                    _hash_node = (*_v)[hash_pos];
                    break;
                }
                ++hash_pos;
            }
            if(hash_pos == _v->size())
                _hash_node = nullptr;
        }
        return *this;
    }
    Self operator++(int)
    {
        Self copy = *this;
        ++(*this);
        return copy;
    }

    bool operator!=(Self another)
    {
        return _hash_node != another._hash_node;
    }

    bool operator==(Self another)
    {
        return _hash_node == another._hash_node;
    }

    Node* _hash_node;
    vector<Node*>* _v;
};

////////////////////////////////////////////////////////////
template <class K, class T, class TOfK, class GetInt, class Comp = Comp<K>>
class HashList
{
public:

    typedef HashListNode<T> Node;
    typedef Hash_Iterator<K, T, TOfK, GetInt> iterator;


    iterator begin()
    {
        for(auto e : _hs)
        {
            if(e != nullptr)
            {
                return iterator(e, &_hs);
            }
        }
        return end();
    }

    iterator end()
    {
        return iterator(nullptr, &_hs);
    }

    HashList()
    {
        _hs.resize(10, nullptr);
    }
    explicit HashList(const size_t size)
    {
        _hs.resize(size, nullptr);
    }
    ~HashList()
    {
        for(auto e : _hs)
        {
            Node* cur = e;
            while(cur)
            {
                e = cur->_next;
                delete cur;
                cur = e;
            }
        }
    }
    size_t size()
    {
        return _n;
    }
    bool empty()
    {
        return _n == 0;
    }
    pair<iterator, bool> insert(const T& val)
    {
        TOfK t_of_k;
        GetInt get_i;

        iterator node = find(val);
        if(node._hash_node)
            return pair<iterator, bool>(node, false);

        if(_n == _hs.size())
        {
            HashList<K, T, TOfK, GetInt> new_hs(_hs.size() * 2);
            for(auto& e : _hs)
            {
                Node *cur = e;
                while (cur)
                {
                    size_t new_pos = get_i(t_of_k(cur->_val)) % new_hs._hs.size();
                    e = cur->_next;
                    cur->_next = new_hs._hs[new_pos];
                    new_hs._hs[new_pos] = cur;
                    cur = e;
                }
            }
            _hs.swap(new_hs._hs);

        }

        size_t hash_pos =  get_i(t_of_k(val)) % _hs.size();
        Node* newnode = new Node(val);
        newnode->_next = _hs[hash_pos];
        _hs[hash_pos] = newnode;
        ++_n;
        return pair<iterator, bool>(iterator(newnode, &_hs), true);
    }

    iterator find(const T& val)
    {
        TOfK t_of_k;
        GetInt get_i;
        Comp compare;
        size_t hash_pos =  get_i(t_of_k(val)) % _hs.size();
        Node* cur = _hs[hash_pos];
        while(cur)
        {
            if(compare(t_of_k(cur->_val), t_of_k(val)))
            {
                return iterator(cur, &_hs);
            }
            cur = cur->_next;
        }
        return iterator(cur, &_hs);
    }

    iterator erase(const T& val)
    {
        TOfK t_of_k;
        GetInt get_i;
        Comp compare;
        size_t hash_pos =  get_i(t_of_k(val)) % _hs.size();
        Node* cur = _hs[hash_pos];
        Node* prev = _hs[hash_pos];
        while(cur)
        {
            if(compare(t_of_k(cur->_val), t_of_k(val)))
            {
                if(cur == _hs[hash_pos])
                    _hs[hash_pos] = cur->_next;
                else
                    prev->_next = cur->_next;

                delete cur;
                --_n;
                return iterator(prev->next, &_hs);
            }
            prev = cur;
            cur = cur->_next;
        }
        return iterator(nullptr, &_hs);
    }
private:
    vector<Node*> _hs;
    size_t _n = 0;

};


//
//namespace OpenHash
//{
//    template<class T>
//    class HashFunc
//    {
//    public:
//        size_t operator()(const T& val)
//        {
//            return val;
//        }
//    };
//
//    template<>
//    class HashFunc<string>
//    {
//    public:
//        size_t operator()(const string& s)
//        {
//            const char* str = s.c_str();
//            unsigned int seed = 131; // 31 131 1313 13131 131313
//            unsigned int hash = 0;
//            while (*str)
//            {
//                hash = hash * seed + (*str++);
//            }
//
//            return hash;
//        }
//    };
//
//    template<class V>
//    struct HashBucketNode
//    {
//        HashBucketNode(const V& data)
//                : _pNext(nullptr), _data(data)
//        {}
//        HashBucketNode<V>* _pNext;
//        V _data;
//    };
//
//    // 本文所实现的哈希桶中key是唯一的
//    template<class V, class HF = HashFunc<V>>
//
//    class HashBucket
//    {
//        typedef HashBucketNode<V> Node;
//        typedef Node* PNode;
//
//        typedef HashBucket<V, HF> Self;
//
//    public:
//        HashBucket()
//                : _table(10, nullptr)
//                , _size(0)
//        {}
//
//        ~HashBucket()
//        {
//            Clear();
//        }
//
//        // 哈希桶中的元素不能重复
//        bool Insert(const V& data)
//        {
//            if(Find(data))
//                return false;
//
//            if(_size == _table.size()) //负载因子达到1了，需要扩容
//            {
//                HF hf;
//                vector<Node*> _new_table(_table.size() * 2, nullptr);
//                for(auto& e : _table)
//                {
//                    if(e)
//                    {
//                        Node* cur = e;
//                        while(cur)
//                        {
//                            size_t pos = hf(cur->_data) % _new_table.size();
//                            e = cur->_pNext;
//                            cur->_pNext = _new_table[pos];
//                            _new_table[pos] = cur;
//                            cur = e;
//                        }
//                    }
//                }
//                _table.swap(_new_table);
//            }
//
//            HF hf;
//            Node* newnode = new Node(data);
//            size_t pos = hf(data) % _table.size();
//            newnode->_pNext = _table[pos];
//            _table[pos] = newnode;
//            ++_size;
//            return true;
//        }
//
//        // 删除哈希桶中为data的元素(data不会重复)
//        bool Erase(const V& data)
//        {
//            if(!Find(data))
//                return false;
//
//            HF hf;
//            int pos = hf(data) % _table.size();
//            Node* cur = _table[pos];
//            Node* prev = nullptr;
//            while(cur)
//            {
//                if(cur->_data == data)
//                {
//                    if(cur == _table[pos])
//                    {
//                        _table[pos] = cur->_pNext;
//
//                    }
//                    else
//                    {
//                        prev->_pNext = cur->_pNext;
//                    }
//                    delete cur;
//                    break;
//                }
//                prev = cur;
//                cur = cur->_pNext;
//            }
//            --_size;
//            return true;
//        }
//
//        Node* Find(const V& data)
//        {
//            HF hf;
//            int pos = hf(data) % _table.size();
//            Node* cur = _table[pos];
//
//            while(cur)
//            {
//                if(cur->_data == data)
//                    return cur;
//                cur = cur->_pNext;
//            }
//
//            return nullptr;
//        }
//
//        size_t Size()const
//        {
//            return _size;
//        }
//
//        bool Empty()const
//        {
//            return 0 == _size;
//        }
//
//        void Clear()
//        {
//            for(auto e : _table)
//            {
//                if(e)
//                {
//                    Node* cur = e;
//                    while(cur)
//                    {
//                        e = cur->_pNext;
//                        delete cur;
//                        cur = e;
//                    }
//                }
//            }
//        }
//
//        size_t BucketCount()const
//        {
//            return _table.capacity();
//        }
//
//        void Swap(Self& ht)
//        {
//            _table.swap(ht._table);
//            swap(_size, ht._size);
//        }
//
//    private:
//        size_t HashFunc(const V& data)
//        {
//            return HF()(data) % _table.capacity();
//        }
//
//        void CheckCapacity();
//
//    private:
//        vector<Node*> _table;
//        size_t _size;      // 哈希表中有效元素的个数
//    };
//}
//
//#include <iostream>
//#include <vector>
//using namespace std;
////我们设计一个哈希结构，必须要清楚什么是哈希
////哈希是一种映射的结构，值与位置的映射
////而哈希表的底层为vector
//enum status //存储节点的状态
//{
//    Empty,
//    Exist,
//    Delete
//};
//
//template <class K>
//struct HashNode
//{
//    K _data;
//    status _sta = Empty;
//};
//
////仿函数
//template <class K>
//class Getint
//{
//public:
//    size_t operator()(const K& data)
//    {
//        return (size_t)data;
//    }
//};
////特化，特别实例化
//template<>
//class Getint<string>
//{
//public:
//    size_t operator()(const string& str)
//    {
//        int ascii = 0;
//        for(auto&e : str)
//        {
//            ascii += e;
//            ascii *= 131;
//        }
//        return ascii;
//    }
//};
//template <class K, class Getint = Getint<K>>
//class HashTable
//{
//public:
//    typedef HashNode<K> Node;
//    HashTable()
//    {
//        _kt.resize(10);
//    }
//
//    HashTable(const int& size)
//    {
//        _kt.resize(size);
//    }
//
//
//    bool erase(const K& data)
//    {
//        HashNode<K>* ret = find(data);
//        if(ret)
//        {
//            --_n;
//            ret->_sta = Delete;
//            return true;
//        }
//        return false;
//    }
//
//    bool insert(const K& data)
//    {
//        //拒绝重复值
//        if(find(data))
//            return false;
//
//        if((double)_n / (double)_kt.size() >= 0.7)
//        {
//            HashTable<K, Getint> new_kt(2 * _kt.size());
//
//            for(auto& e : _kt)
//            {
//                if(e._sta == Exist)
//                {
//                    new_kt.insert(e._data);
//                }
//            }
//            _kt.swap(new_kt._kt);
//        }
//
//        Getint getint;
//        int hash_pos = getint(data) % _kt.size();
//        while(_kt[hash_pos]._sta == Exist)
//        {
//            ++hash_pos;
//            hash_pos %= _kt.size();
//        }
//        _kt[hash_pos]._data = data;
//        _kt[hash_pos]._sta = Exist;
//        ++_n;
//        return true;
//    }
//
//    HashNode<K>* find(const K& data)
//    {
//        Getint getint;
//        int hash_pos = getint(data) % _kt.size();
//        while(_kt[hash_pos]._sta != Empty)
//        {
//            if(_kt[hash_pos]._sta == Exist && _kt[hash_pos]._data == data)
//                return &_kt[hash_pos];
//
//            ++hash_pos;
//            hash_pos %= _kt.size();
//        }
//        return nullptr;
//    }
//private:
//    vector<Node> _kt;
//    size_t _n = 0; //记录哈希表中的有效数据个数
//};